package string;

/**
 * @author Liaorun
 */
public class ParenthesesDeep {


    /**
     * 检查一个字符串中的左右括号是否正确成对
     *
     * @param str
     * @return
     */
    public static boolean isValid(char[] str) {
        if (str == null || str.length == 0) {
            return false;
        }

        int status = 0;

        for (char c : str) {
            if (c != ')' && c != '(') {
                return false;
            }

            if (c == ')' && --status < 0) {
                return false;
            }

            if (c == '(') {
                status++;
            }
        }

        return status == 0;
    }

    /**
     * 检查一个字符串中的左右括号成对的情况下，最大的深度
     * example: ()((())) -> 3; (()) -> 2;
     *
     * @param s
     * @return
     */
    public static int deep(String s) {
        char[] str = s.toCharArray();

        if (!isValid(str)) {
            return 0;
        }

        int count = 0;
        int max = 0;

        for (char c : str) {
            if (c == '(') {
                max = Math.max(max, ++count);
            } else {
                count--;
            }
        }

        return max;
    }


    /**
     * 查找一个全为括号组成的字符串最长的有效括号长度
     * example:)()()() -> 6; ))()(()) -> 6;
     *
     * @param s
     * @return
     */
    public static int maxLength(String s) {
        if (s == null || s.equals("")) {
            return 0;
        }

        char[] str = s.toCharArray();

        int[] dp = new int[str.length];

        int pre = 0;
        int res = 0;

        for (int i = 0; i < str.length; i++) {
            // 当前位置是不是）
            if (str[i] == ')') {
                // 计算应该与之对应的（的位置
                pre = i - dp[i - 1] - 1;
                // 存在这个位置且确实是（
                if (pre > 0 && str[pre] == '(') {
                    // 当前的有效长度为当前）到对应的（的位置 + （前面正常匹配的括号的长度
                    // example: ()(()) ,当 i == 5,pre == 2,
                    // dp[5] = dp[4] + 2 + dp[1] = 2 + 2 + 2 = 6;
                    dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
                }
            }
            res = Math.max(res, dp[i]);
        }

        return res;
    }
}
